1. Field of the Invention
The present invention relates to polygon rendering circuitry of a computer graphics system, and more particularly, to a circuit for determining, to sub-pixel resolution, the coordinates of points along respective edges of a polygon on each scan line covered by the polygon and for filling in the display pixels within the polygon for display.
2. Description of the Prior Art
Prior art raster graphics systems generally contain two distinct parts: a graphics transformation engine that transforms and lights the geometric description of a scene in accordance with the user's viewpoint and a renderer that paints the transformed scene onto a display screen. As is well known, the geometric description of the scene may comprise a combination of a plurality of polygons having an arbitrary number of sides. In other words, the 3-dimensional image to be displayed has been described as a surface composed of polygons of differing shadings. As used herein such a "polygon" refers to an ordered set of vertices V[1] . . . V[N] where N is the vertex count for the polygon. These vertices specify the N edges of the polygon, which are line segments E[1] . . . E[N] with end points made up of respective vertices V[1] . . . V[N]. For example, line segment E[1] may have end points V[1] and V[2], while line segment E[2] has end points V[2] and V[3]. Such polygons may be identified by the graphics transformation engine as a sequence of graphics primitives including information such as the coordinates (X,Y,Z) of the vertices of each polygon as well as the shading information for each of the vertices and instructions which are processed in the graphics transformation engine for all pixel-level rendering computations.
Such geometric representations of a scene greatly facilitate the processing by a graphics transformation engine which is necessary for rendering the pixel image data to the display screen. The graphics transformation engines typically perform many tasks on such data including graphics context management, matrix transformation calculations, spline tessellation and lighting model computations. The transformation engines may also control vector and polygon rendering hardware. However, such computations are generally quite complex and time-consuming and require much processing power. The resulting processing difficulties significantly limit the speed by which images may be rendered in conventional raster graphics systems.
Despite such problems, workstation users are demanding ever-increasing performance and image quality from graphics workstations. This demand produces a corresponding appetite for computing power. One of the most compute-intensive functions of a graphics workstation, besides processing by the graphics transformation engine, is the process of scan conversion, where vector and polygon end points are transformed into pixels on a raster scan display and the pixels appropriately shaded. During the 1980's, a number of 3-D workstations were introduced with hardware scan converters that performed smooth color shading, but all such workstations provided fairly low performance and/or limited feature sets. As a result, designers of such systems often compromised by approximating the correct colors for each pixel by linearly interpolating the colors across each polygon face without correctly accounting for the effect of perspective and by using a simplified polygon sampling method. However, such compromises have been found to cause problems when used in conjunction with advanced features of the type desired for modern day graphics workstations.
Graphics workstations of the 1990's require scan converters which make no such compromises. The increasing complexity of user images requires scan converters capable of generating color, Z (depth), and texture map parameter values in perspective for each pixel in every vector and polygon at a sustained 50M pixels/second (or greater) rate, with peak rates approaching at least 100M pixels/second. Until recently, this level of performance was out of reach due to the complexity of the perspective interpolation algorithms. Indeed, the complexity of perspective-corrected interpolation and texture mapping precluded their hardware implementation, and typically, the correct shading was approximated by implementing linear interpolation of color and Z. However, due to advances in graphics workstation hardware, perspective interpolation and texture mapping are now possible without sacrificing the 100M pixels/second peak rate. For example, a high speed perspective interpolation system is described in U.S. patent application Ser. No. 07/493,189, which was incorporated above by reference, while a high speed texture mapping system is described in U.S. patent application Ser. No. 07/494,706, filed Mar. 16, 1990 and entitled "Method and Apparatus for Generating Textured Graphics Primitives in Frame Buffer Computer Graphics Systems."
Different techniques exist for determining which pixels inside a polygon will be rendered to the display screen by the rendering circuitry. For example, the incrementing fractions interpolation technique permits calculation of the x axis value along the scan line without solving the X=M*Y+C (which requires a multiplication) for each value of Y in the direction perpendicular to the scan line. This is accomplished by computing the line differential, slope M, as a constant equal to (X.sub.end -X.sub.s)/(Y.sub.end -Y.sub.s). Once M has been computed, successive X,Y points can be generated by repeatedly incrementing Y by 1 and adding M to X. All X values are rounded to the nearest integer by adding 0.5 to the initial X value and truncating each X result. However, such a division is generally slow and is prone to round-off errors. Moreover, the fractional part of M and X must have a precision at least equal to the screen precision to be guaranteed of hitting the correct end point. These problems were earlier solved by the present inventor by extending the Bresenham algorithm to polygon rendering.
In particular, the present inventor described in an article entitled "A Fast Shaded-Polygon Renderer", Proceedings of SIGGRAPH '86, Computer Graphics, Vol. 20, No. 4 (August 1986), pp. 95-101, a one-chip VLSI implementation of a shaded-polygon renderer. The polygon renderer described therein takes advantage of an extension to Bresenham's vector drawing algorithm to interpolate four axes (for red, green, blue and Z) across a polygon in addition to the X and Y values. Such a method has provided rendering speeds suitable for interactive manipulation of solids.
As noted above, for most methods of image synthesis, the image is generated by breaking the surfaces of the object into polygons. The color and intensity at each vertex may then be calculated and the results drawn into a frame buffer while interpolating the colors across the polygon. This is known as Gouraud shading. The color information can be calculated from light source data or computed with thermal or stress analysis. The interpolation of coordinate and color (or intensity) across each polygon, on the other hand, is accomplished by interpolating the coordinate and color of each quantized point (pixel) on the edges of the polygon and subsequently interpolating from edge to edge to generate the fill lines. If hidden surface removal with a Z buffer is required, then the depth (Z) value for each pixel must also be calculated. Also, since color components can vary independently across a surface or set of surfaces, red, green, and blue intensities must be interpolated independently. Thus, for a general purpose graphics system, a minimum of 6 different parameters (X, Y, Z, Red, Green, and Blue) must be independently calculated when drawing polygons with Gouraud shading and interpolated Z values. In the aforementioned article, the present inventor teaches extending the line-drawing algorithm proposed by Bresenham to six axes so that the values of X, Y, Z, Red, Green, and Blue may be determined for polygon rendering.
The polygon renderer of that system begins the polygon fill process by reading an instruction and a pointer out of an external dual-ported RAM. The instruction indicates what kind of figure (polygon or vector) is to be drawn and if a line type pattern is to be used. The pointer indicates the location of the first edge data packet for the polygon, and each packet contains a pointer to the next packet. The first pointer is passed to an EDGE functional block. The EDGE block builds up an ordered list of active edges (in the order to be used) and then reads the data packets of the first two edges to be drawn. As they are read, they are passed to a SETUP block and then on to the interpolator. When the interpolator finishes one scan line of each edge, the packets are passed back to the EDGE block. The EDGE block dynamically maintains an active edge list, adding edges as the current scan line reaches them and deleting edges as they are completed. The EDGE block also re-sorts the order of the active edge list whenever two edges cross. This permits the drawing of non-planar, concave, twisted polygons which may contain holes.
As the interpolator steps along each edge in such a polygon rendering system, the output is sampled by a FILL block. The FILL block saves the starting and ending points of each edge's contribution to the scan line. From these values, it generates fill vectors which are passed on to a SETUP block. The FILL block also keeps track of whether or not each edge is just starting or ending so as to properly handle vertices. This polygon fill process will now be described with respect to FIG. 1.
FIG. 1 illustrates a polygon to be rendered and the first four lines of pixels drawn. The pixels in the edge are represented with circles and the pixels making up the fill lines are shown as squares. In this example, once the setup for Edge 1 is complete, its packet of data is sent to the interpolator and the first row of pixels in the edge is drawn. Then the packet is sent to the EDGE block which compares its X and Y values to verify that the third edge does not yet have to be activated. After Edge 2 is set up, its first pixel is drawn and its packet is sent on to the EDGE block. Then, the next horizontal row of pixels in Edge 1 is drawn, followed by the next pixel in Edge 2. As shown, for the second and each subsequent fill line, Edge 1 has several pixels drawn per line, while Edge 2 has only one. The fill line (Fill 1) is then drawn between the inside pixels of each edge. While Fill 1 is being set up, the two edges are again incremented in the Y direction and the next row of pixels in the edges is drawn. The process is repeated for each scan line in the polygon.
Excellent results have been achieved with the abovementioned polygon rendering system. However, since multiple steps sometimes must be used for generating the edge at each scan line, the edge forming process has been found to take a substantial portion of the polygon fill time. Moreover, since the extended Bresenham algorithm renders polygon edges by drawing pixels which lie closest to the true edges, adjacent polygons may overlap or underlap, whereby pixels from backfacing polygons can be seen through gaps between adjacent polygons due to round-off errors. It is desired to minimize this processing time for the edges. It is also desired to precisely identify the edge for each scan line using a very precise point sampling algorithm such that there need only be one pixel for each edge and all pixels therebetween are fill pixels which may be readily interpolated in an efficient manner by the interpolator. In other words, an improved technique for identifying the edges of polygons is desired so that only pixels actually within the polygon edges will be drawn, problems with overlap and underlap will be avoided, and less processing time will be necessary for forming the edges during the polygon rendering process.
Akeley et al. describe in an article entitled "High-Performance Polygon Rendering", Computer Graphics, Vol. 22, No. 4, August 1988, a polygon rendering system architecture for real-time display of shaded polygons. Akeley et al. compute the Y coordinates of the polygon edges to 1/8 pixel tolerance and then correct all depth and color component iterations to the nearest pixel center, which are then iterated in full-pixel steps. Akeley et al. use an Edge Processor to iterate along the top and bottom edges of the trapezoid so as to generate at each iteration the top and bottom coordinates of a single span. Color and depth values are computed using changes in Y to 1/8 pixel accuracy. The slope is then used to iterate to the nearest pixel center. Accordingly, the final span definition comprises the corrected initial color and depth values, the color and depth slopes, the integer X and Y value of the bottom pixel, and the span length.
FIG. 2 shows a polygon ABCD which is rendered in accordance with the technique of Akeley et al. As shown, the polygon ABCD is broken into trapezoids, and the interstitial points X' and X" are determined. The polygon is then filled by using the slope of the edges to iterate with to the nearest pixel center from the edge intersection with the next line. Thus as with the extended Bresenham algorithm, the nearest pixel center is identified as part of the polygon, irrespective of whether that pixel is inside or outside of the polygon being drawn.
The system of Akeley et al. also provides very fast polygon fill rates. However, the system of Akeley et al. requires the determination of the interstitial points X' and X" and only allows the points along the edges to be determined to 1/8 pixel accuracy. Moreover, the polygon is filled by determining the nearest pixel center to each edge and then filling all points in between. As noted above, this approach can result in undesirable polygon overlap and/or a "peek-through" effect wherein gaps are left around the edges of the polygon. Thus, although Akeley, et al. can quickly calculate the edges, their system still has the overlap and underlap problems referred to above.
Accordingly, an improved polygon rendering technique is desired wherein processing speed and accuracy may be enhanced while polygon overlap and undesired "peek-through" effects may be eliminated. The present invention has been designed for this purpose.